package algorithm.sort;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

public class BubbleSort {



    public static void main(String[] args) {
        int[] arr = TestHelp.random(30);
        int[] copyArr = Arrays.copyOf(arr,30);
        // 冒泡排序，
        long begin = TestHelp.begin();
        TestHelp.print(arr);
        bubble(arr);
        TestHelp.end(begin);
        TestHelp.print(arr);
        System.out.println("===============优化===无序==========");
        // 冒泡排序，优化
        begin = TestHelp.begin();
        TestHelp.print(copyArr);
        bubbleOptimize(copyArr);
        TestHelp.end(begin);
        TestHelp.print(copyArr);
        System.out.println("===============优化==有序的数组在排序===========");
        // 冒泡排序，优化
        begin = TestHelp.begin();
        TestHelp.print(arr);
        bubbleOptimize(arr);
        TestHelp.end(begin);
        TestHelp.print(arr);

    }

    /**
     * 冒泡排序
     * 相邻两个元素比较，如果右边更小，则移动到左边（上浮）,一直两两比较到最末元素。即最末元素为最大元素。第二趟重复这个过程，确认倒数第二大元素，循环这个过程
     * 时间复杂度O(n^2) 有两个for循环
     * 空间复杂度O(1) 只需要一个临时空间
     * 稳定算法，相同元素不会变更位置
     * @param arr
     */
    public static void bubble(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {// 表示第几趟
            for (int j = 0; j < arr.length-1-i ; j++) {// 第一趟，找出最大的元素、第二趟找出第二大元素，第三趟找出第三大元素，重复这个过程，直到只有一个元素
                // 按照从小大到排序
                if (arr[j] > arr[j+1]) {// 左边大于右边
                    TestHelp.swap(arr,j,j+1);// 交换

                }
            }
        }
    }

    /**
     * 冒泡排序 优化，如果
     * @param arr
     */
    public static void bubbleOptimize(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {// 表示第几趟
            boolean noSwap = false;// == 优化
            for (int j = 0; j < arr.length-1-i ; j++) {// 第一趟，找出最大的元素、第二趟找出第二大元素，第三趟找出第三大元素，重复这个过程，直到只有一个元素
                // 按照从小大到排序
                if (arr[j] > arr[j+1]) {// 左边大于右边
                    noSwap = true;
                    TestHelp.swap(arr,j,j+1);// 交换

                }
            }
            // 如果没有交换，则表示已排好序
            if(!noSwap){// == 优化
                break;
            }
        }
    }
}
